package offer.day17;

public class No28isSymmetrical {
    /*
     * 面试题28：对称的二叉树
     * 题目：请实现一个函数，用来判断一颗二叉树是不是对称的。
     * 如果一棵二叉树和它的镜像一样，那么它是对称的。
     * 例如：8->(left)2  8->(right)2  对称的
     * 	   8->(left)3  8->(right)2 非对称的
     *
     *
     * 思路：使用递归的思想
     * 使用两个相同的二叉树，从根节点开始，比较其左右子树的根节点值是否相等，不想等，返回false；
     * 相等的话，继续比较  看是否左节点值 = 右节点值并且右节点值 = 左节点值
     * 。。。。。。继续比较，直到比较到为空  或者是不想等，或者是叶子节点为止，同时到达叶子节点，则证明是对称的，返回true；
     * 但是若一个到了叶子节点，但是另一个没有到达，证明不是对称的 ，返回false
     * 递归内容：1>结束内容（条件）：若是两个都为空指针，则返回true
     * 						若两个其中一个为空指针（到达叶子节点），则返回false
     * 						若是两个值不想等，则返回false
     * 		  2>数据库处理内容： 无（判断两个值是否相等）
     * 		  3>递归调用内容：将左子树，右子树    或者    右子树，左子树再进行判断是否对称，重复之前的操作。
     * */

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        No28isSymmetrical s = new No28isSymmetrical();

        BinaryTreeNode root1 = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(8);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(9);
        BinaryTreeNode four = new BinaryTreeNode(2);
        BinaryTreeNode five = new BinaryTreeNode(4);
        BinaryTreeNode six = new BinaryTreeNode(7);

        root1.left = one;
        root1.right = two;
        one.left = three;
        one.right = four;
        two.left = null;
        two.right = null;
        three.left = null;
        three.right = null;
        four.left = five;
        four.right = six;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        if (s.isSymmetrical(root1)) {
            System.out.println("二叉树是对称的！");
        } else {
            System.out.println("二叉树不是对称的！！！！");
        }
    }

    private boolean isSymmetrical(BinaryTreeNode root) {
        return isSymmetrical(root, root);
    }

    private boolean isSymmetrical(BinaryTreeNode root1, BinaryTreeNode root2) {
        if (root1 == null && root2 == null) return true;
        if (root1 == null || root2 == null) return false;
        if (root1.val != root2.val) return false;
        return isSymmetrical(root1.left, root2.right) && isSymmetrical(root1.right, root2.left);
    }
}
